/**
 * @file   QuickSort.h
 * @author Shao <student@student>
 * @date   Sun Dec 12 13:35:54 2021
 * 
 * @brief  
 * 
 * 
 */

#include<iostream>
#include<vector>
#include<algorithm>

#ifndef QUICKSORT_H
#define QUICKSORT_H

using namespace std ;

template <typename Compareble>
void quick_sort(vector<Compareble>& a, int begin, int end ) ;
/*
 * 插入排序。
 */
template <typename Compareble>
void insertionsort(vector<Compareble>& a, int begin, int end )
{
	for(int i = begin+1 ; i <= end ; ++ i )
	{
		int s = a[i] ;
		int j = i-1   ;
		while(j >=begin && s < a[j])
		{
			a[j + 1] = a[j];
			--j;
		}
		a[j+1] = s ;
	}
}
template<typename Compareble>
void quick_sort(vector<Compareble>& object)
{
	quick_sort(object, 0, object.size() - 1);
}
/*
 * 三取中值法，枢纽元的选取。
 */
template<typename Compareble>
const Compareble & median3(vector<Compareble> & a, int begin, int end)
{
	int center = (begin + end) / 2;
	if (a[center] < a[begin])
		swap(a[center], a[begin]);
	/*
	 * 将最小的元素放到vector的开头，符合要求。
	 */
	if (a[end] < a[begin])            
        swap(a[begin], a[end]);
	/*
	 * 将最小的元素放到vector的末尾，符合要求。
	 */
    if (a[end] < a[center])        
        swap(a[center], a[end]);
    
	/*
	 * 将枢纽元放在末尾左侧一个的位置上，符合要求。
	 */
	swap(a[center], a[end - 1]);
	return a[end - 1];
}

template <typename Compareble>
void quick_sort(vector<Compareble> & a, int begin, int end)
{
    if (begin + 10 <= end)
    {
        Compareble pivot = median3(a, begin, end);
		int left = begin;
		int right = end - 1;
		while(1)
		{
			while(a[++left] < pivot )	{ } 
			while(pivot < a[--right])	{ }
			if(left < right ){
				swap(a[left], a[right]);
			}
				else break;
		}

		swap(a[left], a[end - 1]);
		quick_sort(a, begin, left - 1);
		quick_sort(a, left + 1, end);
	}
	else
	{
		insertionsort(a, begin, end );
	}
}

#endif
